#ifndef SOLUTION_H_INCLUDED
#define SOLUTION_H_INCLUDED

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    using matrix = vector<vector<int>>;
    static void print(std::ostream &os, vector<int> &vec) {
        for (auto v : vec) {
            os << v << ",";
        }
        os << endl;
    }

    static void print(std::ostream &os, matrix &mat) {
        for (auto &vec : mat) {
            print(os, vec);
        }
    }

    int numWays(int n, vector<vector<int>>& relation, int k) {
        matrix mat;
        mat.resize(n);

        for (auto &vec : relation) {
            mat[vec[0]].push_back(vec[1]);
        }

        print(cout, mat);

        vector<int> route;
        route.push_back(0);
        int c = 0;
        for (auto i : mat[0]) {
            dfs(mat, i, n, k-1, c, route);
        }
        return c;
    }

    void dfs(const matrix &mat, int i, int n, int k, int &c, vector<int> route) {
        route.push_back(i);
        if ((k == 0) && (i == n - 1)) {
            ++c;
            print(cout, route);
            return;
        }

        if (k <= 0) {
            return;
        }

        k -= 1;

        for (auto j : mat[i]) {
            dfs(mat, j, n, k, c, route);
        }
    }
};

#endif /* SOLUTION_H_INCLUDED */
